#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;


//乘积为正数的最长子数组长度
//https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/submissions/
//class Solution {
//public:
//    int getMaxLen(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> f(n), g(n);
//
//        if (nums[0] > 0) f[0] = 1, g[0] = 0;
//        else if (nums[0] < 0)  f[0] = 0, g[0] = 1;
//
//        int maxnum = f[0];
//        for (int i = 1; i < n; ++i)
//        {
//            if (nums[i] > 0)
//            {
//                f[i] = f[i - 1] + 1;
//                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
//            }
//            else if (nums[i] < 0)
//            {
//                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
//                g[i] = f[i - 1] + 1;
//            }
//            if (f[i] > maxnum) maxnum = f[i];
//        }
//        return maxnum;
//    }
//};



//等差数列划分
//https://leetcode.cn/problems/arithmetic-slices/
// class Solution {
// public:
//     int numberOfArithmeticSlices(vector<int>& nums) {
//         int n = nums.size();
//         if(n<3) return 0;

//         vector<int> v(n);
//         int num = 0;
//         for(int i = 2;i<n;++i)
//         {
//             //判断前三个是否能组成等差数列 如果可以就加上前面已组成的值 如果不行就为0
//             v[i] = nums[i-1]-nums[i-2] == nums[i]-nums[i-1]?v[i-1]+1:0;
//             num += v[i];
//         }
//         return num;
//     }
// };


//最长湍流子数组
//https://leetcode.cn/problems/longest-turbulent-subarray/submissions/
// class Solution {
// public:
//     int maxTurbulenceSize(vector<int>& arr) {
//         int n = arr.size();
//         if(n == 1) return 1;
        
//         //我们以i位置为结尾 求最长湍流子数组
//         //当到达i位置时 i-1 < i或 i-1 > i 或 i-1 == i
//         //以为结尾可能呈上升趋势也可能呈下降趋势， 所以使用两个dp数组表示上升和下降趋势数组
//         //f[i]:表示以i位置为结尾时 i与i-1构成 上升 趋势的子数组数
//         //g[i]:表示以i位置为结尾时 i与i-1构成 下降 趋势的子数组数

//         //       i<i-1 当前位置呈下降趋势，则此时不满足上升结尾，这个数组单独成为一个子数组 置为1
//         //f[i]:  i>i-1 当前位置呈上升趋势，满足条件，此时i-1与i-2一定要构成下降趋势，所以置为g[i-1]+1
//         //       i==i-1 如果相等 则这个数组单独成为一个子数组 置为1

//         //       i<i-1 当前位置呈下降趋势，满足条件，此时i-1与i-2一定要构成上升趋势，所以置为f[i-1]+1
//         //g[i]:  i>i-1 当前位置呈上升趋势，则此时不满足下降结尾，这个数组单独成为一个子数组 置为1
//         //       i==i-1 如果相等 则这个数组单独成为一个子数组 置为1

//         //我们发现，除了上升和下降趋势 其他情况子数组都为1 所以我们初始化可以将数组全部初始化为1
//         vector<int> f(n,1),g(n,1);
//         int num = 0;
//         for(int i = 1;i<n;++i)
//         {
//             if(arr[i] > arr[i-1]) //上升趋势
//                 f[i] = g[i-1]+1;
//             else if(arr[i] < arr[i-1]) //下降趋势
//                 g[i] = f[i-1]+1;

//             num = num>f[i]?num>g[i]?num:g[i]:f[i]>g[i]?f[i]:g[i];
//         }
//         return num;
//     }
// };